KVS (Key-Value Store) refers to a database technique or database that provides a function corresponding to associative array in programming languages. In other words, the KVS manages a set of key and data, by making an arbitrary key correspond to the data (or value) that is a management target. An access to the data may be made by specifying the key. Distributed KVS refers to a format in which a placement location of the set of key and data is distributed to a plurality of nodes.
In the distributed KVS, the space (hereinafter referred to as “hash space”) in which hash values of the keys are mapped is segmented and allocated to each of the nodes. Consistent hashing is one known method of segmenting the hash space. According to the consistent hashing, a range (hereinafter referred to as “covering range”) covered by each node within the hash space is determined by the hash value of an identification name (for example, server name) of each node. For example, suppose that three nodes A, B, and C exist, and that the hash value of the server name of the node A is “10”, the hash value of the server name of the node B is “40”, and the hash value of the server name of the node C is “90”. A total range of the hash space may be regarded to be greater than or equal to 0 and less than or equal to 100.
In this case, the covering range (or responsible range) of the node A is greater than or equal to 10 and less than 40. The covering rage of the node B is greater than or equal to 40 and less than 90. The covering range of the node C is greater than or equal to 90 and less than 100, and greater than or equal to 0 and less than 10. This state of the nodes A, B, and C may be represented as illustrated in FIG. 1, for example.
FIG. 1 is a diagram illustrating an example of segmenting the hash space based on the consistent hashing. A circumference H in FIG. 1 illustrates the hash space that is the management target. Circles labeled A, B, and C on the circumference H denote the nodes A, B, and C. A range Ha denotes the covering rage of the node A, a range Hb denotes the covering range of the node B, and a range Hc denotes the covering range of the node C.
A client computes the hash value of the key of the data that is the access target, and issues an access request with respect to the node that includes the hash value within the covering range thereof.
The applicants are aware of Japanese Laid-Open Patent Publications No. 2008-233968, No. 2006-92322 (or Japanese Patent No. 4281658), No. 2007-323668, and No. 2005-50303 (or Japanese Patent No. 4418286).
In the case of the consistent hashing, the covering range of each node is fixedly determined based on the server name and the like of each node. For this reason, as may be seen from FIG. 1, a relatively large unbalance may occur in the sizes of the covering ranges among the nodes. As a result, a state may easily occur in which the data or the load concentrates at a certain node, however, such a state may be difficult to cure.